Auflistung nach Schlagwort "Descriptive complexity"

Auflistung nach Schlagwort "Descriptive complexity"

Sortiert nach: Sortierung: Ergebnisse:

  • Dependence logic with a majority quantifier 
    Durand, Arnaud; Ebbing, Johannes; Kontinen, Juha; Vollmer, Heribert (Wadern : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, 2011)
    We study the extension of dependence logic D by a majority quantifier M over finite structures. We show that the resulting logic is equi-expressive with the extension of second-order logic by second-order majority quantifiers ...
  • Descriptive complexity of #AC0 functions 
    Durand, Arnaud; Haak, Anselm; Kontinen, Juha; Vollmer, Heribert (Saarbrücken : Dagstuhl Publishing, 2016)
    We introduce a new framework for a descriptive complexity approach to arithmetic computations. We define a hierarchy of classes based on the idea of counting assignments to free function variables in first-order formulae. ...